home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / umich / falcon / programm.ing / nt_dsp1.lzh / NT_DSP1.MSA / FFT / FFTR2CC.HLP < prev    next >
Text File  |  1990-01-17  |  4KB  |  62 lines
  1.          Name: FFTR2CC.ASM
  2.          Type: Assembler Macro
  3.       Version: 1.0
  4.   Last Change:  18-Aug-88
  5.  
  6.   Description: Radix 2, In-place, Decimation-in-time Complex FFT Macro
  7.  
  8.  This macro is a slightly faster version of the macro FFTR2C. It uses a
  9.  special pipelining technique which overlaps butterflies to obtain faster
  10.  overall execution, at a small cost in extra program length. The remaining
  11.  part of this description is identical to the one of the macro FFTR2C.
  12.  
  13.  This macro performs a complete Fast Fourier Transform (FFT) on complex
  14.  data.  The basic algorithm is the Decimation-in-time (DIT), Radix 2
  15.  FFT algorithm using 24 bit fixed-point arithmetic.  The algorithm uses
  16.  a sine-cosine lookup table for the FFT coefficients (twiddle factors).
  17.  FFTR2CC can be called to perform any FFT from 16-32768 points.  Simply
  18.  call it with the arguments of number of FFT points, location of the
  19.  data array and location of the sine-cosine table.  All register
  20.  initialization is performed by this macro.  However, the macro assumes
  21.  that registers which should not be altered by the FFT have already been
  22.  saved by the main program.  This allows the user to fit the FFT macro
  23.  into his application and thus control the context switching overhead.
  24.  No data scaling is performed and no overflow detection is done.
  25.  Modifications to this routine could allow it to be used with the
  26.  scaling modes and thus allow dynamic scaling for each FFT pass.
  27.  
  28.  All data and coefficients are complex, with the real part in X Data
  29.  memory and the imaginary part in Y Data memory.  For an N point FFT,
  30.  the data buffer requires N X Data and N Y Data memory locations.
  31.  The algorithm is performed "in-place", meaning that only one data
  32.  buffer is required for both input and output data.  The input
  33.  data is assumed to be in normal (time-sequential) order and the
  34.  output is in bit-reversed order.  By using the reverse-carry
  35.  address modifier and a separate output data buffer, the output
  36.  data may be easily unscrambled.  Other methods also exist to
  37.  unscramble the output data without a separate output data buffer. 
  38.  The FFTR2CC macro uses "twiddle factors" (-cosine and -sine tables)
  39.  stored in data memory.  For maximum speed, the FFT macro performs
  40.  a lookup table operation to get new sine and cosine values for
  41.  each group of butterflies.  A SINCOS macro is available to
  42.  generate these tables.  For an N point FFT, N/2 X Data and N/2
  43.  Y Data locations are required.  Sine and cosine values could be
  44.  calculated in real-time to save data memory at the expense of
  45.  execution time.
  46.  
  47.  The FFTR2CC macro is faster than the FFTR2A and FFTR2B library
  48.  macros.  The speed increase is obtained by performing the first
  49.  two passes in one combined operation without storing the results
  50.  of the first pass.  The first two passes do not require any
  51.  multiplies since the coefficients are -1, 0 or +1.  The last pass
  52.  is also split out from the triple nested DO loop and given a separate
  53.  DO loop (identical to the FFTR2B macro).  The reason this is faster
  54.  is that the inner loop always starts with a loop count of 1 on the
  55.  last pass.  Note that the separate last pass DO loop uses different
  56.  addressing modes to increment through the butterflies, thus avoiding
  57.  outer loops.  Additional details are included in the source file;
  58.  however, more algorithm description would be required for complete
  59.  understanding by typical users.  The FFTR2CC macro can directly
  60.  replace the FFTR2A macro using the calling procedure shown in the
  61.  FFTR2AT test program.
  62. ^Z